package com.example.demo.leetcode.top;

/**
 *一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
 *
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
 *
 * 问总共有多少条不同的路径？
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/unique-paths
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 */
public class Array_不同路径 {


    /**
     *
     * 使用动态规划:
     * 第一一个二维数组:
     *      1.数组的存储的值为:机器人抵达当前位置的路径数量,
     *      2.并且有一个规则，抵达当前位置的路径数量为: 左边+右边的总路劲数量
     *      3.上边界和左边界都给 1
     * @param m
     * @param n
     * @return
     */

    public static int uniquePaths(int m, int n) {
        int [][] arr = new int[m][n];
        for(int i=0;i<m;i++){
            arr[i][0]=1;
        }
        for(int i=0;i<n;i++){
            arr[0][i]=1;
        }

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(j-1<0 || i-1<0){
                    continue;
                }else{
                    arr[i][j]=arr[i][j-1]+arr[i-1][j];
                }
            }
        }
        return arr[m-1][n-1];

    }

    /**
     *    x   x1  x1  x1  x1  x1     x1
     *    x1  x2  x3  x4  x5  x6     x7
     *    x1  x3  x6  x10  x15  x21  x28
     * @param m
     * @param n
     * @return
     */


    public static void main(String[] args) {
        System.out.println( uniquePaths(3,7));
    }


}
